// 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

// 注意:
// 每个数组中的元素不会超过 100
// 数组的大小不会超过 200


// 暴露接口
const canPartition = function (nums: number[]): boolean {
    let sum: number = 0;
    for (let num of nums) {
        sum += num;
    }
    if (sum % 2 !== 0) return false;
    const hashMap = new Map<string, boolean>();
    return canPartition_DFS(nums, sum / 2, 0, 0, hashMap);
};

function canPartition_DFS(nums: number[], target: number, currIndex: number,
    currSum: number, hashmap: Map<string, boolean>): boolean {
    const key = currSum + ',' + currIndex; // 描述一个情况的key至少要包含两个状态
    // 递归出口：如果当前的情况有被计算过
    if (hashmap.has(key)) {
        return hashmap.get(key)!;
    }
    // 递归出口：指针越界 or 超出目标和
    if (currIndex === nums.length || currSum > target) {
        return false;
    }
    // 如果当前和等于目标值则直接返回
    if (currSum === target) return true;
    // 哈希表记录情况
    const res =
        canPartition_DFS(nums, target, currIndex + 1, currSum + nums[currIndex], hashmap) ||
        canPartition_DFS(nums, target, currIndex + 1, currSum, hashmap);
    hashmap.set(key, res);
    return res;
}

// 这道题按照常规思路解决其实是一个利用深度优先遍历相关的递归设计问题
// 我们需要把这道题的理解转换一下，变成：
// 给你一个非空数组，数组和为sum，能否找到一个子序列，和为sum / 2
// 1.如果sum为奇数，肯定找不到，因为sum/2为小数，而数组只包含正整数，子序列的和也为整数。
// 2.如果sum为偶数，有可能找到。
// 而对于数组中的每个单元素，只用2种情况
// 1.选择中当前这个元素，基于选它，对下一个索引元素继续选（递归）
// 2.不选择这个元素，基于不选它，对下一个索引元素继续选（递归）
// 而我们思考递归的出口情况：
// 1.指针越界，考察完所有元素，始终没有返回true，于是返回false，即没有找到满足条件的子序列。
// 2.当前和 > 目标值，当前的累加和已经超了，不用继续选数字了，终止递归，返回false。
// 3.当前和 == 目标值，正好满足条件，不用继续选数字了，终止递归，返回true。
// 但这里如果直接这样使用的话存在一个问题，就是在面对大元素的时候递归计算时间非常久
// 所以可以采取记忆化递归的方式，用空间来换时间
// 而对于每一种情况，我们都有利用当前的索引和当前和两种状态来对这个子问题进行描述
// （选不选中当前元素得到的当前和是一样的，所以这个key值的设计需要思考）
// 这样我们在递归的过程中，如果发现当前情况已经被计算过，那么直接用哈希表返回就好了，避免了子树重复计算
